package com.TheEndWork.fifthDay;

import java.util.HashSet;

/**
 * @authoer zsj
 * @date 2022/5/27 14:44
 */
public class alg {
    /**
     * leecode 876
     * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
     * 如果有两个中间结点，则返回第二个中间结点。
     */
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode middleNode(ListNode head) {
        //思路：快慢指针,慢指针一次走一步，快指针一次走两步，当快指针走到了尽头，慢指针就走了一半，返回慢指针的所指向节点即可
        ListNode slow = head;
        ListNode fast = head;
        //如果有两个中间节点返回第二个节点我们就需要判断两个节点的下一个节点是不能为空的
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * leecode 19
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //如何找到这倒数第n个节点,然后将这个节点的前一个的next改为这个节点的next,就完成了删除
        //利用双指针思想,先让快指针走n步,然后两个指针在一起走,当快指针的next==null的时候,慢指针也就指向了我们要删除的节点的位置
        ListNode slow = head, fast = head;
        ListNode newHead = new ListNode(0,head);

        //先让快指针先走
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        //判断一下现在的fast是不是为空的
        if (fast == null){
            //如果现在的fast是空的，说明要删除的是头节点
            return newHead.next.next;
        }
        //然后两个指针一起走
        while (fast !=null){
            slow = slow.next;
            fast =fast.next;
        }
        slow.next = slow.next.next;
        return newHead.next;
    }

    public ListNode removeNthFromEnd2(ListNode head, int n) {
        //如何找到这倒数第n个节点,然后将这个节点的前一个的next改为这个节点的next,就完成了删除
        ListNode dummy  = new ListNode(0, head);
        int length = getLength(head);
        ListNode temp = dummy;
        for (int i = 1; i < length - n + 1; i++) {
            temp = temp.next;
        }
        //现在的temp的后一个就是我们要剔除的元素
        temp.next = temp.next.next;
        return dummy.next;
    }

    /**
     * 获取链表长度的方法
     */
    public int getLength(ListNode node) {
        int length = 0;
        while (node.next != null) {
            node = node.next;
            length++;
        }
        return length;
    }
}
